Date modified: Thu 2023-05-11 . 11:51 AM
Date created: Sat 2023-10-07 . 09:02 PM
# General position in chess: No-three-in-line problem. Try this. On an $8\times 8$ chess board, can you put $16$ pawns such that no three of them are in a line? By line we mean ANY line, **not just** horizontal, vertical, or $45^\circ$ lines. We often say a set of points in the plane is in **general position** if no three points are in a line. So here we are looking for general positions of pawns in an $n\times n$ chess board. Given $n$, what is the **largest number** of pieces you can put in general position on an $n\times n$ chess board? ![[Excalidraw/General position in chess no three in line problem 2023-05-07 14.37.20.excalidraw.svg]] Now by pigeonhole principle, on an $n\times n$ chess board, if you have more than $2n$ pieces, then there will be three pieces in a line. Indeed, since there are only $n$ rows, putting $2n+1$ pieces would make one of them row having three or more pieces. So we know at best we can put $2n$ pieces on an $n \times n$ board so that no three will be in a line. But is this always possible? For example can you put 6 pieces of pawns on a $3\times 3$ chess board so that no three of them are in a line? How about $8$ pieces on a $4\times 4$ chess board? Or $16$ pieces on a regular $8\times8$ chess board? --- Let us denote $T_n$ to be the maximum number of pieces you can put on an $n\times n$ chess board so that no three are in a line. As it turns out, $T_n = 2n$ for $2 \le n \le 46$ or so, and it is (as of my understanding in 2023) **unknown** whether $2n$ can always be realized for much larger $n$ ! It is an open question in discrete geometry, the **no-three-in-line problem**. Note, when the board gets larger, more possible lines you need to consider, not just the multiples of $45^\circ$ degree lines! Below are some maximal configurations for $n=3,4,5,6,7$. What about $n=8$. ![[Excalidraw/General position in chess no three in line problem 2023-05-07 15.09.21.excalidraw.svg]] ![[Excalidraw/General position in chess no three in line problem 2023-05-07 23.18.14.excalidraw.svg]] ![[Excalidraw/General position in chess no three in line problem 2023-05-07 23.22.54.excalidraw.svg]] %%[[Excalidraw/General position in chess no three in line problem 2023-05-07 23.22.54.excalidraw.md|🖋 Edit in Excalidraw]], and the [[Excalidraw/General position in chess no three in line problem 2023-05-07 23.22.54.excalidraw.dark.svg|dark exported image]]%% Can you write a computer code to generate these? #chess #discrete-geometry #i-dont-know-the-answer